#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/13 14:09
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _17_letterCombinations.py
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        res = []
        if not  digits: return res

        def dfs(index, combination):
            if index == len(digits):
                res.append(combination[:])
                return
            for c in phone[digits[index]]:
                dfs(index+1, combination+c)
        dfs(0,"")
        return res

